\documentclass[unicode]{beamer}
\mode<presentation>
\usepackage{beamerthemesplit}
\usetheme{Malmoe}
%\usepackage[cp1251]{inputenc}
\usepackage[english]{babel}
%\usepackage[T2A]{fontenc}
\usepackage{amssymb,amsfonts,amsmath}
\usepackage {array}
\usepackage{graphicx}
\usepackage {gastex}
\usepackage{algorithm,algpseudocode}
\usepackage[]{color}%,dvips
\usepackage{pstricks,pst-node,pst-text}%,pst-3d
\definecolor{emp}{rgb}{0.2, 0.4, 0.4}
\definecolor{tr}{rgb}{0,0.5,0}
\definecolor{orng}{rgb}{1, 0.5, 0}
\definecolor{db}{rgb}{0,0,0.7}


\algtext*{EndWhile}% Remove "end while" text
\algtext*{EndIf}% Remove "end if" text
\algtext*{EndFunction}% Remove "end function" text
\algtext*{EndProcedure}% Remove "end procedure" text
\algtext*{EndFor}% Remove "end for" text

\let\OldComment\Comment
\renewcommand{\Comment}[1]{\OldComment{\textcolor{gray}{#1}}}



\author[D. Kosolobov, M. Rubinchik, A. Shur]{\emph{Dmitry Kosolobov}, Mikhail Rubinchik, and Arseny Shur}
\title[Finding Distinct Subpalindromes Online]{Finding Distinct Subpalindromes Online}

\institute[]{Ural Federal University\\ Ekaterinburg, Russia}
\begin{document}
\date{ }
\maketitle

\section{Definitions and Problem}

\begin{frame}
\frametitle{Introduction}
\begin{itemize}
\item<1-> A \emph{palindrome} is a string that is equal to its reversal; for example, the string $\blue aabcbaa$ is a palindrome
\item<2-> A \emph{subpalindrome} of a string is a substring that is a palindrome
\end{itemize}
\vspace{1em}
\begin{itemize}
\item<3-> The well-known \emph{Sturmian words} are characterized by their \emph{palindromic complexity} (de Luca 1997, Droubay, Pirillo, 1999)
\item<3-> There are several papers on the properties of \emph{rich words}, see Glen, Justin, Widmer, Zambony (2009) (a word $w$ with $|w|{+}1$ distinct subpalindromes is called \emph{rich}).
\item<3-> The class of rich words includes the \emph{episturmian words} introduced by Droubay, Justin, Pirillo (2001).
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Problem}
\uncover<2->{
Every string of length $n$ contains at most $n{+}1$ distinct subpalindromes, including the empty string (Droubay, Justin, Pirillo, 2001).}
\vspace{1em}

\uncover<3->{\textbf{Can one find all distinct subpalindromes of a string in linear time and space?}}

\vspace{1em}
\uncover<4->{This question was answered in the affirmative with an \textcolor{db}{offline} algorithm (Groult, Prieur, Richomme, 2010). In that paper, the existence of the corresponding \textcolor{db}{online} algorithm was stated as an open problem.}
\end{frame}

\section{Main Result}

\begin{frame}
\begin{theorem}
There exists an online algorithm which finds all distinct subpalindromes in a string over a finite alphabet $\Sigma$ in time 
\begin{itemize}
\item $O(n|\Sigma|)$ if $\Sigma$ is unordered,
\item $O(n\log|\Sigma|)$ if $\Sigma$ is ordered,
\end{itemize}
using linear space.

This algorithm is optimal in the comparison based computation model.
\end{theorem}
\end{frame}

\begin{frame}
\begin{lemma}[Groult, Prieur, Richomme, 2010]
The set of all distinct subpalindromes of a string coincides with the set of longest palindromic suffixes of all prefixes of this string.
\end{lemma}

\begin{block}{Example}
The set of all subpalindromes of the string $\blue aacba$ is $\{a,b,c,aa\}$.
$$\begin{array}{cc}
\text{\bf prefix} & \text{\bf longest palindromic suffix}\\
a & a\\
aa & aa\\
aac & c\\
aacb & b\\
aacba & a
\end{array}
$$
\end{block}
\end{frame}

\begin{frame}
\frametitle{Manacher's algorithm (1975)}
\begin{itemize}
\item<2-> A palindrome of even (resp. odd) length is referred to as an \emph{even} (resp. \emph{odd}) palindrome.
\item<3-> The location of a subpalindrome in a string is determined by two numbers, \emph{center} and \emph{radius}:
\centerline{
\unitlength=0.9mm
\begin{picture}(93,17)(-18,-2)
\gasset{Nw=5,Nh=5,Nmr=0,AHnb=0}%Nfill=y,
\drawline(0,0)(75,0)
\drawline(0,5)(75,5)
\drawpolygon[linecolor=green,linewidth=0.5](10,0)(65,0)(65,5)(10,5)
\node(2)(12.5,2.5){\textcolor{blue}{$a$}}
\node(3)(37.5,2.5){\textcolor{blue}{$b$}}
\node(4)(62.5,2.5){\textcolor{blue}{$a$}}
\multiput(5,2.5)(21.7,0){4}{\makebox(0,0)[cc]{\small$\cdots$}}
\node[Nframe=n](c)(37.5,11.5){center}
\drawedge[AHnb=1](c,3){}
\put(-5,2.5){\makebox(0,0)[rc]{odd subpalindromes:}}
\put(22.5,5.5){\makebox(0,0)[cc]{$\overbrace{\phantom{aaaaaaaaaaaa}}$}}
\put(22.5,9){\makebox(0,0)[cb]{radius}}
\end{picture}}
\centerline{
\unitlength=0.9mm
\begin{picture}(93,16.5)(-18,-2)
\gasset{Nw=5,Nh=5,Nmr=0,AHnb=0}%Nfill=y,
\drawline(0,0)(75,0)
\drawline(0,5)(75,5)
\drawpolygon[linecolor=green,linewidth=0.5](10,0)(65,0)(65,5)(10,5)
\node(2)(12.5,2.5){\textcolor{blue}{$a$}}
\node(03)(35,2.5){\textcolor{blue}{$b$}}
\node(3)(40,2.5){\textcolor{blue}{$b$}}
\node(4)(62.5,2.5){\textcolor{blue}{$a$}}
\multiput(5,2.5)(21.7,0){4}{\makebox(0,0)[cc]{\small$\cdots$}}
\node[Nframe=n](c)(40,11.5){center}
\drawedge[AHnb=1](c,3){}
\put(-5,2.5){\makebox(0,0)[rc]{even subpalindromes:}}
\put(23.75,5.5){\makebox(0,0)[cc]{$\overbrace{\phantom{aaaaaaaaaaaaa}}$}}
\put(23.75,9){\makebox(0,0)[cb]{radius}}
\end{picture}}

\item<4-> Manacher's algorithm for odd (resp. even) palindromes computes online for the string $text[1..n]$ the array $Rad[1..n]$ such that $Rad[j]$ is the radius of the longest odd (resp. even) subpalindrome of $text[1..n]$ centered at $j$.
\end{itemize}


\end{frame}

\begin{frame}
\frametitle{Manacher's algorithm pseudocode}
The following modification of Manacher's algorithm computes online the longest odd palindromic suffix of a string. The algorithm for even case is analogous.
\begin{algorithmic}[1]
	\Procedure{AddLetter}{$c$}
	\EndProcedure
		\State $s \gets i{-}Rad[i]$\Comment{$i$ is the center of $text[1..n]$ max odd suf-pal} \label{lst:line:calcs}
        \State $text[n{+}1] \gets c$ \Comment{append $c$ to $text[1..n]$}
		\While{$i{+}Rad[i] \leqslant n$}\label{lst:line:forbeg}
			\State $Rad[i] \gets \min(Rad[s{+}n{-}i], n{-}i)$\Comment{$Rad[i]$ in $text[1..n]$}\label{lst:line:min}
			\If{$i + Rad[i] = n \mathrel{\mathbf{and}} text[i{-}Rad[i]{-}1] = c$}\label{lst:line:breadth}
				\State $Rad[i] \gets Rad[i] + 1$\Comment{extending the max suf-pal}
				\State $\mathbf{break}$     \Comment{max odd suf-pal of $text[1..n{+}1]$ found}
			\EndIf
            \State $i \gets i + 1$ \Comment{next candidate for the center}
		\EndWhile\label{lst:line:forend}
		\State $n \gets n + 1$ \Comment{$i$ is the center of max odd suf-pal of $text[1..n]$}
\end{algorithmic}
\end{frame}

\begin{frame}
\frametitle{Example}

\centerline{
\unitlength=1mm
\begin{picture}(75,31)(-25,-4)
\gasset{Nw=5,Nh=5,Nmr=0}
\multiput(0,20)(0,5){2}{\line(1,0){50}}
\multiput(0,20)(5,0){11}{\line(0,1){5}}
\put(-5,22.5){\makebox(0,0)[rc]{$w=$}}
\put(2.5,21){\makebox(0,0)[cb]{a}}
\put(7.5,21){\makebox(0,0)[cb]{b}}
\put(12.5,21){\makebox(0,0)[cb]{a}}
\put(17.5,21){\makebox(0,0)[cb]{d}}
\put(22.5,21){\makebox(0,0)[cb]{a}}
\put(27.5,21){\makebox(0,0)[cb]{a}}
\put(32.5,21){\makebox(0,0)[cb]{d}}
\put(37.5,21){\makebox(0,0)[cb]{c}}
\put(42.5,21){\makebox(0,0)[cb]{a}}
\put(47.5,21){\makebox(0,0)[cb]{a}}
\visible<2->{
\multiput(0,0)(5,0){11}{\line(0,1){15}}
\multiput(0,0)(0,5){4}{\line(1,0){50}}
\put(-5,12.5){\makebox(0,0)[rc]{$Rad_{odd}$}}
\put(-5,7.5){\makebox(0,0)[rc]{$Rad_{even}$}}
\put(-5,2.5){\makebox(0,0)[rc]{$LenPalSuf$}}
}
\visible<3->{
\put(2.5,11){\makebox(0,0)[cb]{0}}
\put(7.5,11){\makebox(0,0)[cb]{1}}
\put(12.5,11){\makebox(0,0)[cb]{0}}
\put(2.5,6){\makebox(0,0)[cb]{0}}
\put(7.5,6){\makebox(0,0)[cb]{0}}
\put(12.5,6){\makebox(0,0)[cb]{0}}
\put(2.5,1){\makebox(0,0)[cb]{1}}
\put(7.5,1){\makebox(0,0)[cb]{1}}
\put(12.5,1){\makebox(0,0)[cb]{3}}
\put(17.5,1){\makebox(0,0)[cb]{1}}
}
\visible<3-4>{ \put(17.5,11){\makebox(0,0)[cb]{\blue 0}} }
\visible<3-6>{ \put(17.5,6){\makebox(0,0)[cb]{\blue 0}} }
\visible<3>{ \put(22.5,21){\makebox(0,0)[cb]{\blue a}} }
\visible<4-5>{
\put(12.5,21){\makebox(0,0)[cb]{\green a}}
\put(22.5,21){\makebox(0,0)[cb]{\green a}}
}
\visible<5-9>{ \put(17.5,11){\makebox(0,0)[cb]{\blue 1}} }
\visible<6>{
\put(17.5,21){\makebox(0,0)[cb]{\red d}}
\put(22.5,21){\makebox(0,0)[cb]{\red a}}
}
\visible<7->{ \put(17.5,6){\makebox(0,0)[cb]{0}} }
\visible<7-11>{ \put(22.5,6){\makebox(0,0)[cb]{\blue 0}} }
\visible<8->{ \put(22.5,1){\makebox(0,0)[cb]{3}} }
\visible<8>{ \put(27.5,21){\makebox(0,0)[cb]{\blue a}} }
\visible<9>{
\put(27.5,21){\makebox(0,0)[cb]{\red a}}
\put(7.5,21){\makebox(0,0)[cb]{\red b}}
\drawcurve[linewidth=0.2](12.5,14)(17.5,16.5)(22.5,14)
}
\visible<10->{ \put(17.5,11){\makebox(0,0)[cb]{1}} }
\visible<10>{
\put(27.5,21){\makebox(0,0)[cb]{\red a}}
\put(17.5,21){\makebox(0,0)[cb]{\red d}}
\put(22.5,11){\makebox(0,0)[cb]{\blue 0}}
}
\visible<11-13>{ \put(27.5,11){\makebox(0,0)[cb]{\blue 0}} }
\visible<11->{ \put(22.5,11){\makebox(0,0)[cb]{0}} }
\visible<12-14>{ \put(22.5,6){\makebox(0,0)[cb]{\blue 1}} }
\visible<12>{
\put(27.5,21){\makebox(0,0)[cb]{\green a}}
\put(22.5,21){\makebox(0,0)[cb]{\green a}}
}
\visible<13->{ \put(27.5,1){\makebox(0,0)[cb]{2}} }
\visible<13>{ \put(32.5,21){\makebox(0,0)[cb]{\blue d}} }
\visible<14>{
\put(32.5,21){\makebox(0,0)[cb]{\red d}}
\put(22.5,21){\makebox(0,0)[cb]{\red a}}
}
\visible<14-16>{ \put(32.5,11){\makebox(0,0)[cb]{\blue 0}} }
\visible<14->{ \put(27.5,11){\makebox(0,0)[cb]{0}} }
\visible<15>{
\put(32.5,21){\makebox(0,0)[cb]{\green d}}
\put(17.5,21){\makebox(0,0)[cb]{\green d}}
}
\visible<15-16>{ \put(22.5,6){\makebox(0,0)[cb]{\blue 2}} }
\visible<16->{ \put(32.5,1){\makebox(0,0)[cb]{4}} }
\visible<16>{ \put(37.5,21){\makebox(0,0)[cb]{\blue c}} }
\visible<17->{
\put(32.5,11){\makebox(0,0)[cb]{0}}
\put(37.5,11){\makebox(0,0)[cb]{0}}
\put(42.5,11){\makebox(0,0)[cb]{0}}
\put(47.5,11){\makebox(0,0)[cb]{0}}
\put(22.5,6){\makebox(0,0)[cb]{2}}
\put(27.5,6){\makebox(0,0)[cb]{0}}
\put(32.5,6){\makebox(0,0)[cb]{0}}
\put(37.5,6){\makebox(0,0)[cb]{0}}
\put(42.5,6){\makebox(0,0)[cb]{0}}
\put(47.5,6){\makebox(0,0)[cb]{1}}
\put(37.5,1){\makebox(0,0)[cb]{1}}
\put(42.5,1){\makebox(0,0)[cb]{1}}
\put(47.5,1){\makebox(0,0)[cb]{2}}
}
\end{picture}}

\visible<18>{The last array gives us the multiset containing all subpalindromes of $w$:
$$
\{a,b,aba,d,ada,aa,daad,c,a,aa\}.
$$
\textbf{How to remove all repetitions from this multiset?} }
\end{frame}

\begin{frame}
\frametitle{Ukkonen's tree}
Ukkonen's algorithm builds online the compressed suffix tree of a string. The algorithm requires $O(\log |\Sigma|)$ amortized time to append one letter to a string over alphabet $\Sigma$.

\centerline{
\unitlength=1mm
\begin{picture}(40,36)(0,-5)
\gasset{Nw=1,Nh=1,Nfill=y,AHnb=0,ELdist=0.3}%
\node(o)(20,25){}
\node(a)(11.5,19){}
\node(ba)(20,11){}
\node(cba)(38.7,11.8){}
\node(acba)(11.5,3){}
\node(aacba)(-8.9,4.6){}
\gasset{Nw=0,Nh=0,Nfill=n}
\node(b)(20,18){}
\node(c)(28.5,19){}
\node(cb)(30.2,17.8){}
\node(ac)(11.5,12){}
\node(acb)(11.5,10){}
\node(aa)(3,13){}
\node(aac)(1.3,11.8){}
\node(aacb)(-0.4,10.6){}
\drawedge[ELside=r](o,a){a}
\drawedge[ELpos=80](o,b){b}
\drawedge[ELpos=25](b,ba){a}
\drawedge[ELpos=80](o,c){c}
\drawedge(c,cb){b}
\drawedge[ELpos=20](cb,cba){a}
\drawedge[ELpos=75](a,ac){c}
\drawedge(ac,acb){b}
\drawedge[ELpos=30](acb,acba){a}
\drawedge[ELpos=80,ELside=r](a,aa){a}
\drawedge[ELside=r](aa,aac){c}
\drawedge[ELside=r](aac,aacb){b}
\drawedge[ELpos=20,ELside=r](aacb,aacba){a}
\put(20,0){\makebox(0,0)[ct]{The compressed suffix tree for the word $aacba$}}
\end{picture}}
%\begin{figure}[h]
%\centering
%\includegraphics[scale=0.5]{suffixTree}
%\end{figure}

\end{frame}

\begin{frame}
Ukkonen's algorithm efficiently implements the parameter $minUniqueSuff$: the length of the minimal suffix of the processed string such that this suffix occurs in this string only once (Ukkonen, 1995).

\vspace{1em}
We don't interest in suffix tree itself we only need $minUniqueSuff$ to verify whether the suffix of a string has another occurrence in this string.
\end{frame}

\begin{frame}
\frametitle{Example (continued)}

\centerline{
\unitlength=1mm
\begin{picture}(75,26)(-25,1)
\gasset{Nw=5,Nh=5,Nmr=0}
\multiput(0,20)(0,5){2}{\line(1,0){50}}
\multiput(0,20)(5,0){11}{\line(0,1){5}}
\put(-5,22.5){\makebox(0,0)[rc]{$w=$}}
\put(2.5,21){\makebox(0,0)[cb]{a}}
\put(7.5,21){\makebox(0,0)[cb]{b}}
\put(12.5,21){\makebox(0,0)[cb]{a}}
\put(17.5,21){\makebox(0,0)[cb]{d}}
\put(22.5,21){\makebox(0,0)[cb]{a}}
\put(27.5,21){\makebox(0,0)[cb]{a}}
\put(32.5,21){\makebox(0,0)[cb]{d}}
\put(37.5,21){\makebox(0,0)[cb]{c}}
\put(42.5,21){\makebox(0,0)[cb]{a}}
\put(47.5,21){\makebox(0,0)[cb]{a}}
\visible<2->{
\multiput(0,5)(5,0){11}{\line(0,1){10}}
\multiput(0,5)(0,5){3}{\line(1,0){50}}
\put(-5,12.5){\makebox(0,0)[rc]{$LenPalSuf$}}
\put(-5,7.5){\makebox(0,0)[rc]{$MinUniqueSuff$}}
\put(2.5,11){\makebox(0,0)[cb]{1}}
\put(7.5,11){\makebox(0,0)[cb]{1}}
\put(12.5,11){\makebox(0,0)[cb]{3}}
\put(17.5,11){\makebox(0,0)[cb]{1}}
\put(22.5,11){\makebox(0,0)[cb]{3}}
\put(27.5,11){\makebox(0,0)[cb]{2}}
\put(32.5,11){\makebox(0,0)[cb]{4}}
\put(37.5,11){\makebox(0,0)[cb]{1}}
\put(42.5,11){\makebox(0,0)[cb]{1}}
\put(47.5,11){\makebox(0,0)[cb]{2}}
\put(2.5,6){\makebox(0,0)[cb]{1}}
\put(7.5,6){\makebox(0,0)[cb]{1}}
\put(12.5,6){\makebox(0,0)[cb]{2}}
\put(17.5,6){\makebox(0,0)[cb]{1}}
\put(22.5,6){\makebox(0,0)[cb]{2}}
\put(27.5,6){\makebox(0,0)[cb]{2}}
\put(32.5,6){\makebox(0,0)[cb]{3}}
\put(37.5,6){\makebox(0,0)[cb]{1}}
\put(42.5,6){\makebox(0,0)[cb]{2}}
\put(47.5,6){\makebox(0,0)[cb]{3}}
}
\visible<3->{
\put(2.5,11){\makebox(0,0)[cb]{\blue 1}}
\put(7.5,11){\makebox(0,0)[cb]{\blue 1}}
\put(12.5,11){\makebox(0,0)[cb]{\blue 3}}
\put(17.5,11){\makebox(0,0)[cb]{\blue 1}}
\put(22.5,11){\makebox(0,0)[cb]{\blue 3}}
\put(27.5,11){\makebox(0,0)[cb]{\blue 2}}
\put(32.5,11){\makebox(0,0)[cb]{\blue 4}}
\put(37.5,11){\makebox(0,0)[cb]{\blue 1}}
\put(42.5,6){\makebox(0,0)[cb]{\red 2}}
\put(47.5,6){\makebox(0,0)[cb]{\red 3}}
}
\end{picture}}
\visible<3->{The longest palindromic suffixes of the two longest prefixes of $w$ do not contribute to the set of distinct subpalindromes.}

\end{frame}


\section{Lower Bounds}

\begin{frame}
\frametitle{Insert-only dictionary}
A \emph{dictionary} is a data structure $D$ containing some set of elements from a given universe and designed for fast implementation of the basic operations like
\begin{itemize}
\item checking the membership of an element in the set;
\item deleting an existing element;
\item adding a new element.
\end{itemize}

\uncover<2->{An \emph{insert-only dictionary} supports only the operation $\mathrm{insqry}(x)$, which checks membership and, if $x$ is not in the dictionary, adds it.}

\vspace{0.5em}
\uncover<3->{\begin{lemma}
Suppose that the alphabet $\Sigma$ consists of indivisible elements, $n\ge |\Sigma|$, and the insert-only dictionary $D$ over $\Sigma$ is initially empty. Then the sequence of $n$ calls of $\mathrm{insqry}$ requires, in the worst case, $\Omega(n\log|\Sigma|)$ time if $\Sigma$ is ordered and $\Omega(n|\Sigma|)$ if $\Sigma$ is unordered.
\end{lemma}}
\end{frame}

\begin{frame}
\begin{itemize}
\item We reduce the problem of maintaining an insert-only dictionary to counting distinct palindromes in a string, thus proving the required lower bounds for the problem of finding (or even just counting) distinct subpalindromes.
\item<2-> We assume that we have a black box algorithm that processes an input string letter by letter and outputs, after each step, the number of distinct palindromes in the string read so far.
\item<3-> We can assume that the considered black box algorithm works in time $O(n\cdot f(m))$, where $m$ is the size of the alphabet of the processed string and the function $f(m)$ is non-decreasing.
\end{itemize}
\end{frame}


\begin{frame}
\begin{lemma}
Suppose that $a,b$ are two different letters and $w=abx_1abx_2\cdots abx_n$ is a string such that each $x_i$ is a letter different from $a$ and $b$. Then all nonempty subpalindromes of $w$ are single letters.
\end{lemma}
\end{frame}


\begin{frame}
\frametitle{Maintaining an insert-only dictionary}
Let us describe how to process a sequence of $n$ calls $\mathrm{insqry}(x_1),\ldots,\mathrm{insqry}(x_n)$ starting from the empty dictionary. Suppose that $x_i \notin \{a,b\}$ for every $i$.

\begin{itemize}
\item<2-> We feed the black box with $a$, $b$, and $x_i$ (in this order). 
\item<3-> We get the output of the black box and check whether the number of distinct subpalindromes in its input string increased.
\item<4-> By Lemma, the increase happens if and only if $x_i$ appears in the input string of the black box for the first time. Thus, we can immediately answer the query ``$x_i\in D$?'', and, moreover, $x_i$ is now in the dictionary.
\end{itemize}

\uncover<5->{The overall time bound is $O(n\cdot f(m))$. We obtain $f(m)=\Omega(\log m)$ (resp., $f(m)=\Omega(m)$) in the case of ordered (resp., unordered) alphabet $\Sigma$.}
\end{frame}

\section{Conclusion}

\begin{frame}
\frametitle{Conclusion}
Our approach shows that it is hardly possible to design a linear time and space online algorithm for the discussed problem even in stronger natural computation models such as the word-RAM model or cellprobe model. The reason is the resource restrictions of dictionaries. However, up to the moment we have proved no nontrivial lower bounds for the insert-only dictionary in more sophisticated models than the comparison based model.
\end{frame}

\begin{frame}
\center{\Huge{Thank you for your attention!}}
\end{frame}

\end{document}